# -*- coding: utf-8 -*-
"""
Classes and function to test Tre-GARP where Tre is some preorder. 
The main function garp_NOQ takes a N x L matrix of consumption C,
a N x L matrix of prices P, a list of generators each which take a consumption bundle 
and return an iterator over the increasing closure of the provided bundle. The list
is called Ilist. The I stands for increasing closure. The function takes an argument
called e which represents the efficiency level to test.
"""

import numpy as np

def _array_in_list(my_array,my_list):
    '''Tests if the numpy array is in the list provided.'''
    return next((True for elem in my_list if np.array_equal(elem, my_array)), False)

class RP_Manager_NOQ():
    '''Class to manage the revealed preference relations.
    Initialize with the C,P, Ilist, and e. Call with two integers n,m and will
    determined if n is e-rp to m.'''
    
    def __init__(self,C,P,Ilist,e):
        N, L = C.shape
        self.A = np.array( [[ -1 for n in range(N) ] for n in range(N) ] )
        #-1 in A[n,m] means have not determined if n is e-rp to m.
        self.Ilist = Ilist
        self.N = N
        self.e = e
        self.C = C
        self.P = P
        
    def __call__(self,n,m):
        '''returns True if n is directly rp to m. Otherwise False.'''
        
        #see if we have already figured out if n is e-rp to m.
        if self.A[n,m] == -1:
            #visited holds list of consumption bundles in the increasing closure
            #of C[m] which we have tested.
            visited = []
            #queue holds the list of bundles in the increasing closure of C[m]
            #which we still have to test.
            #Turn bundles into tuples cuz the x in L works strangely for arrays.
            queue = [self.C[m]] 
            while len(queue):
                #cbass is the current element in the increasing closure of C[m]
                #which we are testing.
                cbass = queue.pop()
                #See if cbass is in e-budget set of ob n.
                if (self.P[n] @ ( self.e * self.C[n] - cbass ) ) > 0.:
                    #We found a bundle in the e-budget set of ob n
                    #which is in the increasing closure of C[m].
                    self.A[n,m] = 1
                    break
                #Add cbass to visited.
                visited.append(cbass)
                #For each increasing closure function in Ilist we need to get the
                #bundles which are above cbass.
                for I in self.Ilist:
                    #Icbass is a generator of bundles which are weakly better than cbass.
                    Icbass = I(cbass)
                    for cupper in Icbass:
                        #cupper is a bundle in the increasing closure of cbass.
                        #If cupper is not in visited and not in queue then add
                        #it to the queue.
                        if ( not _array_in_list(cupper,visited) ) & ( not _array_in_list(cupper,queue) ):
                            #add cupper to the queue
                            queue.append(cupper)
            #If we have not set A[n,m] to 1 then it should be 0.
            if self.A[n,m] == -1:
                self.A[n,m] = 0
        return bool(self.A[n,m])   
                
        
def _trivial_gen(x):
    yield x        


def garp_NOQ( C,P, Ilist = None, e = 1.0 ):
    '''Pass two N x L matrices. C is the consumption matrix and P is the price matrix.
    There are N observations and L goods. Ilist is a list of generators of the
    increasing closure of a bundle. e is the efficiency score to check.'''
    
    N, L = C.shape
    
    if Ilist == None:
        Ilist = [_trivial_gen]
    
    #RP is used to determine if ob n is rp to ob m.
    RP = RP_Manager_NOQ(C,P,Ilist,e)
    
    #This loop will see if there are any cycles.
    for n in range(N):
        #Check if there is a cycle involving ob n.
        visited = N * [False] #If an element enters here we disregard it.
        queue = [n] #Observations left to check.
        while len(queue):
            m = queue.pop() #We will see what ob m is e-revealed preferred to
            for i in range(n,N):
                #The for loop does not consider obs we know aren't in a cycle.
                if visited[i] == False: #Only check out obs that haven't been visited
                    if RP(m,i): #See if rp
                        #m is e-revealed preferred to i
                        if i == n: #If i is n then we've found a cycle
                            return False
                        queue.append(i) #We know there's a path from obnum to i. 
                        visited[i] = True
    return True
    

def garp_NOQ_find_e( C,P, Ilist = None):
    '''C and P are N x L matrices where N is the number of obs and L is the 
    number of goods. C represents the consumption bundles and P the prices. 
    Ilist is a list of genetors which take a consumption bundle and return
    iterate over the bundles which are weakly better than the provided bundle.
    Finds the efficiency level at which the data just passes e-GARP-NOQ.'''
    
    if Ilist == None:
        Ilist = [_trivial_gen]
    
    high_e = 1.0
    low_e = 0.0
    e = 1.0
    #Will binary search until we have narrowed the window enough.
    while high_e - low_e >= 2**(-15):
        if garp_NOQ( C,P,Ilist, e ):
            low_e = e #Our e passes so raise the lower bound.
        else:
            high_e = e #Our e failed so lower the upper bound.
        e = (high_e + low_e) / 2.0 #New e is the midpoint.
    return e
    
 